/**
 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

 示例 1:

 输入: 1->1->2
 输出: 1->2
 示例 2:

 输入: 1->1->2->3->3
 输出: 1->2->3
 */
class Solution {

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    /**
     * 虚拟头节点
     */
//    public ListNode deleteDuplicates(ListNode head) {
//        ListNode dummyHead = new ListNode(-1);
//
//        dummyHead.next = head;
//        ListNode prev = head;
//        while (prev.next != null){
//            if(prev.val == prev.next.val){
//                prev.next = prev.next.next;
//                prev = prev.next;
//            }
//        }
//
//        return head;
//    }

    /**
     *递归
     */
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        head.next = deleteDuplicates(head.next);
        if(head.val == head.next.val) head = head.next;
        return head;
    }
}